Brezhnev gặp Nikita Khrushchev năm 1931, một thời gian ngắn sau khi vào Đảng. Ông trở thành người được Khrushchev bảo trợ và tiếp tục thăng tiến của các cấp bậc lãnh đạo. Ông là Bí thư thứ nhất của Đảng tại Cộng hoà Xã hội chủ nghĩa Xô viết Moldavia từ ngày 3 tháng 11 năm 1950 tới 16 tháng 4 năm 1952. Với tư cách Bí thư thứ nhất Đảng Cộng sản Moldavia, Brezhnev loại trừ và trục xuất hàng nghìn người sắc tộc Romania khỏi Cộng hoà Xã hội chủ nghĩa Xô viết Moldavia và thực hiện việc tập thể hóa bắt buộc. Trong thời Brezhnev ở đây, ông chịu trách nhiệm việc chuyển 25 vạn người khỏi Cộng hoà Xã hội chủ nghĩa Xô viết Moldavia tới các vùng khác của Liên Xô.

Stalin chết tháng 3 năm 1953, và trong tiến trình tái tổ chức sau khi Đoàn chủ tịch bị xoá bỏ và một Bộ chính trị nhỏ hơn được tái lập. Dù Brezhnev không được làm một thành viên Bộ chính trị, ông được chỉ định làm Phó tổng cục trưởng Tổng cục Chính trị Hồng quân và Hải quân với cấp bậc Trung tướng, một chức vụ rất cao cấp. Đây có lẽ bởi quyền lực mới của người đỡ đầu cho ông - Khrushchev, đã thành công trong việc lên thay thế Stalin trở thành Tổng bí thư Đảng. Ngày 7 tháng 5 năm 1955, ông trở thành Bí thư thứ nhất của Đảng Cộng sản Cộng hoà Xã hội chủ nghĩa Xô viết Kazakh, cũng là một chức vụ quan trọng.

Tháng 2 năm 1956, Brezhnev được gọi về Moskva, đưa lên làm Ủy viên dự khuyết Bộ chính trị và chịu trách nhiệm kiểm soát ngành công nghiệp quốc phòng, chương trình không gian, công nghiệp nặng, và xây dựng thủ đô. Khi ấy ông là một thành viên cao cấp trong bộ máy của Khrushchev, vào tháng 6 năm 1957, ông ủng hộ Khrushchev trong cuộc đấu tranh của ông này với nhóm thân Stalin trong giới lãnh đạo đảng, cái gọi là "Nhóm Chống Đảng" do Vyacheslav Molotov, Georgy Malenkov, Lazar Kaganovich cũng như Dmitri Shepilov đứng đầu. Sau khi đánh bại nhóm đảng viên già, Brezhnev trở thành một Ủy viên chính thức của Bộ chính trị. Tháng 5 năm 1960, ông được bầu làm Chủ tịch Đoàn chủ tịch Xô viết Tối cao, khiến ông được chỉ định làm nguyên thủ quốc gia dù quyền lực thực tế nằm trong tay Khrushchev với tư cách Tổng bí thư.

Cho tới tận khoảng năm 1962, chức vụ của Khrushchev là lãnh đạo Đảng vẫn vững chắc, nhưng khi già thêm ông trở nên thất thường và cách lãnh đạo của ông khiến ông mất lòng tin trong giới lãnh đạo. Các vấn đề kinh tế ngày càng nghiêm trọng của Liên Xô cũng làm gia tăng sức ép lên chức vụ lãnh đạo của Khrushchev. Bề ngoài, Brezhnev vẫn hoàn toàn trung thành với Khrushchev, nhưng, vào năm 1963, ông tham gia vào một âm mưu loại bỏ Khrushchev, có lẽ theo một số nguồn tin chính là người tổ chức âm mưu, như lời kể của Gennadii Voronov[6]. Alexey Kosygin, Nikolay Podgorny, Alexander Shelepin và một số quan chức cao cấp khác cũng tham dự vào kế hoạch. Năm ấy Brezhnev kế vị Frol Kozlov, một người được đỡ đầu khác của Khrushchev, làm Bí thư thứ hai Ban chấp hành Trung ương Đảng Cộng sản Liên Xô, khiến ông trở thành người có khả năng kế vị Khrushchev.

Ngày 14 tháng 10 năm 1964, khi Khrushchev đang đi nghỉ, những người âm mưu hành động. Brezhnev và Podgorny triệu tập Bộ chính trị, lên án Khrushchev về những sai lầm trong kinh tế, buộc tội ông là người duy ý chí và có cách cư xử không đúng đắn. Bị ảnh hưởng bởi đồng minh của Brezhnev, các Ủy viên Bộ chính trị bỏ phiếu loại bỏ Khrushchev. Brezhnev được chỉ định làm Bí thư thứ nhất của Đảng; Aleksey Kosygin được chỉ định làm Thủ tướng, và Anastas Mikoyan trở thành lãnh đạo nhà nước (Năm 1965 Mikoyan nghỉ hưu và được thay thế bởi Podgorny).